package 表达式运算_中缀;

public class 表达式运算_中缀 {

	public static void main(String[] args) {
		//表达式
		//String experssion = "3+2*6-2"; //13
		//String experssion = "6/2+5-1"; //7
		String experssion = "60/2+5*100"; //7
		//数栈
		ArrayStack numStack = new ArrayStack(10);
		//符号栈
		ArrayStack operStack = new ArrayStack(10);
		//用来遍历的索引
		int index = 0;
		//接收 pop 出的第一个数，运算符右侧数
		int num1 = 0;
		//接收 pop 出的第二个数，运算符左侧数
		int num2 = 0;
		//遍历的结果
		char ch = ' ';
		//取出的运算符
		char oper = ' ';
		//结果
		int res = 0;
		//用于拼接多位数
		String keepNum = "";
		
		while(true) {
			//得到 ex 每一个字符
			ch = experssion.charAt(index);
			
			//如果是符号
			if(operStack.isOper(ch)) {
				//1.如果符号栈为空
				if(operStack.isEmpty()) {
					//直接入栈
					operStack.push(ch);
					System.out.println("空，入栈");
				}else {
				//2.符号栈不为空，比较操作符
					//2.1如果当前操作符优先级 小于等于 栈顶操作符，
					//取出 两个数一个操作符 运算后，入数栈，当前运算符 入符栈
					if(operStack.priority(ch) <= operStack.priority((char)operStack.peek())) {
						//取出两个数
						num1 = numStack.pop();
						num2 = numStack.pop();
						//取出一个运算符
						oper = (char) operStack.pop();
						res = numStack.cal(num1, num2, oper);
						System.out.println(num2+" "+oper+" "+num1 +"="+res);
						//结果入栈
						numStack.push(res);
						
						//操作符入栈
						operStack.push(ch);
					}else {
					//2.2如果当前操作符优先级 大于 栈顶操作符，入栈，等待右边数字运算
						operStack.push(ch);
					}
				}
			
				
		    //不是符号，是数字
			}else {
				//不考虑多位数
				
				//如果是个位数，直接入栈，ch 是char 类型ASCII，需要-48，或者转int
				//numStack.push(ch-48);
				
				//考虑多位数
				keepNum += ch;
				//判断是否最后一位，如果是最后一位，直接入栈
				if(index == experssion.length()-1) {
					numStack.push(Integer.parseInt(keepNum));
				}else {
					//判断，只判断一次，如果还有只能下一次判断
					if(operStack.isOper(experssion.charAt(index+1))) {
						numStack.push(Integer.parseInt(keepNum));
						keepNum = "";
					}
					
				}
				
			}
			
			
			//增加index，继续循环
			index++;
			if(index >= experssion.length()) {
				break;
			}
		}
		
		
		//表达式扫描完，操作符是同一优先级，顺序取出所有数字和符号运算
		while(true) {
			//操作符取完，数栈只剩最后一个结果
			if(operStack.isEmpty()) {
				break;
			}
			//取出两个数
			num1 = numStack.pop();
			num2 = numStack.pop();
			//取出一个运算符
			oper = (char) operStack.pop();
			res = numStack.cal(num1, num2, oper);
			System.out.println(num2+" "+oper+" "+num1 +"="+res);
			//结果入栈
			numStack.push(res);
		}
		
		//数栈最后一个是结果
		System.out.println("---"+numStack.pop());
		
	}
}

//利用数组栈计算表达式，添加几个方法
class ArrayStack{
	private int maxSize;
	private int[] stack;
	private int top;
	
	public ArrayStack() {
		super();
	}

	public ArrayStack(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[maxSize];
		top = -1;
	}
	
	//判断是否运算符
	public boolean isOper(char val) {
		return val == '+' || val == '-' || val == '*' || val == '/';
	}
	
	//返回运算符优先级，数字越大，优先级越高
	public int priority(char oper) {
		
		if(oper == '+' || oper == '-') {
			return 0;
		}else if(oper == '*' || oper == '/') {
			return 1;
		}else {
			return -1;
		}
	}
	
	//运算
	public int cal(int num1, int num2, char ch) {
		//结果
		int res = 0;
		//注意运算顺序，num1是第一个pop出的数字，num2是第二个pop出数字，
		//运算从左向右，左边数字先入栈，后出栈，右边数字后入栈，先出栈
		//注意 - 和 / 
		switch (ch) {
		case '+':
			res = num1+num2;
			break;
		case '-':
			res = num2-num1;
			break;
		case '*':
			res = num1*num2;
			break;
		case '/':
			res = num2/num1;
			break;
		default:
			break;
		}
		return res;
	}
	
	//查看栈顶元素
	public int peek() {
		return stack[top];
	}
	
	//栈空
	public boolean isEmpty() {
		return top == -1;
	}
	//栈满
	public boolean isFull() {
		return top == maxSize - 1;
	}
	
	//入栈
	public void push(int data) {
		if(isFull()) {
			System.out.println("栈满！");
			return;
		}
		
		top++;
		stack[top] = data;
	}
	
	//出栈
	public int pop() {
		if(isEmpty()) {
			throw new RuntimeException("栈空！");
		}
		
		int data = stack[top];
		top--;
		return data; 
	}
	
	//显示栈，从栈顶开始，就是数组尾部
	public void showStack() {
		if(isEmpty()) {
			System.out.println("栈空！");
			return ;
		}
		
		for(int i = top; i >= 0;i--) {
			System.out.println("stack["+ stack[i] +"]");
		}
	}
}